package 力扣.堆;


import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

class ListNode{
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class 合成k个升序链表23 {
    public static void main(String[] args) {
        ListNode listNode1a = new ListNode(1);
        ListNode listNode1b = new ListNode(4);
        ListNode listNode1c = new ListNode(5);
        listNode1a.next = listNode1b;
        listNode1b.next = listNode1c;

        ListNode listNode2a = new ListNode(1);
        ListNode listNode2b = new ListNode(3);
        ListNode listNode2c = new ListNode(4);
        listNode2a.next = listNode2b;
        listNode2b.next = listNode2c;

        ListNode listNode3a = new ListNode(2);
        ListNode listNode3b = new ListNode(6);
        listNode3a.next = listNode3b;

        ListNode[] lists ={listNode1a,listNode2a,listNode3a};
        ListNode listNode = mergeKLists2(lists);
    }
// 前提是有序，所以选用小根堆。直接看方法3
    public static ListNode mergeKLists(ListNode[] lists) {
        LinkedList<Object> list = new LinkedList<>();
        ListNode ans = new ListNode();
        for (ListNode li : lists ) {
            while ( li !=null){
                list.add(li.val);
                li = li.next;
            }
        }
//        System.out.println(list);
        Integer[] nums = list.toArray(new Integer[0]);
        for (int i = nums.length - 2; i >= 0; i--) {//构造小根堆
            adjust(nums,i, nums.length);
        }
        ListNode te = ans;
        for (int i = nums.length - 1; i >= 0; i--) {//每次选择最小的一个元素
            ListNode listNode = new ListNode(nums[0]);
            te.next = listNode;
            te = te.next;
            swap(nums,0,i);
            adjust(nums, 0,i);
        }
        te.next = new ListNode(nums[0]);
        return ans.next;
    }

    private static void swap(Integer[] nums, int i, int i1) {
        int te = nums[i];
        nums[i] = nums[i1];
        nums[i1] = te;
    }
//构建小根堆
    private static void adjust(Integer[] nums, int i,int length) {
        int te = nums[i];
        for (int j = (i << 1) + 1; j < length; j = (j << 1) + 1) {//找到最小的孩子节点
            if (j < length - 1 && nums[j+1] < nums[j]){
                j++;
            }
            if (nums[j] < te){
                nums[i] = nums[j];
                i = j;
            }else {
                break;
            }
        }
       nums[i] = te;
    }

    /**解法二：
     * 直接使用优先队列和堆排序效果一样
     * @param lists
     * @return
     */
    public static ListNode mergeKLists2(ListNode[] lists) {
        ListNode ans = new ListNode();

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;//极小堆
            }
        });
        for (ListNode li : lists ) {
            while ( li !=null){
                priorityQueue.offer(li.val);
                li = li.next;
            }
        }
        int len = priorityQueue.size();
        ListNode te = ans;
        for (int i = len; i > 0; i--) {
            ListNode listNode = new ListNode(priorityQueue.poll());
            te.next = listNode;
            te = te.next;
        }
        return ans.next;
    }

    public static ListNode mergeKLists3(ListNode[] lists) {
        if (lists == null || lists.length == 0){
            return null;
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;//小根堆
            }
        });
        ListNode ans = new ListNode(0);
        ListNode tmp = ans;
        for (ListNode li : lists ) {//选出每个链表的头
            if (li != null){
                pq.offer(li);
            }
        }
        while (!pq.isEmpty()){
            tmp.next = pq.peek();//取出最小的元素
            if (pq.peek().next != null){//链表的下一个节点就去
               pq.add(pq.poll().next);
            }else {
                pq.poll();
            }
            tmp = tmp.next;
        }
        return ans.next;

    }
}
